package _11_binary_search_tree.exerc;

import _11_binary_search_tree.BSTree;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/13 - 21:29
 * leetcode 题：
 * 根据前序遍历结果构建树
 * 8, 5, 1, 7, 10, 12
 *
 *              8
 *             /\
 *            5  10
 *           /\   \
 *          1  7   12
 *
 * 前提：数组最小长度为1，并且元素不能重复
 */
public class LeetCodeTest {
    @Test
    public void test() {
        int[] arr = {8, 5, 1, 7, 10, 12};

        BSTree r =  buildTree1(arr);
        BSTree r2 =  buildTree2(arr);
        BSTree r3 =  buildTree3(arr);

        System.out.println(r);
        System.out.println(r2);
        System.out.println(r3);
    }

    /**
     * 方式一
     */
    private BSTree buildTree1(int[] arr) {
        BSTree tree = new BSTree();
        tree.root = new BSTree.BSTNode(arr[0]);
        for (int i = 0; i < arr.length; i++) {
            build(tree.root, arr[i]);
        }
        return tree;
    }

    private BSTree.BSTNode build(BSTree.BSTNode node, int i) {
        if(node == null) {
            return new BSTree.BSTNode(i);
        }
        if(i < node.key) {
            node.left = build(node.left, i);
        } else if(i > node.key) {
            node.right = build(node.right, i);
        } else {
            // 如果内容重复处理
        }
        return node;
    }


    /**
     * 方式二 上限法
     */
    private BSTree buildTree2(int[] arr) {
        BSTree tree = new BSTree();
        tree.root = insert(arr, Integer.MAX_VALUE);
        return tree;
    }

    private int adder = 0; // 或者使用 AtomicInteger
    private BSTree.BSTNode insert(int[] arr, int max) {
        if(adder == arr.length) {
            return null;
        }

        int key = arr[adder];
        if(key > max) {
            return null;
        }
        BSTree.BSTNode node = new BSTree.BSTNode(key);
        adder++;
        node.left = insert(arr, key);
        node.right = insert(arr, max);
        return node;
    }


    /**
     * 方式三 分治法
     * 8, 5, 1, 7, 10, 12
     * 根8 左5,1,7 右10,12  第一个元素就是根，往后比根小的是左子树，比根大的是右子树（只需找到第一个比它大的就行，后面的都会比它大）
     * 根5 左1 右7
     * 根10 左null 右12
     */
    private BSTree buildTree3(int[] arr) {
        BSTree tree = new BSTree();
        tree.root = forkJoin(arr, 0, arr.length - 1);
        return tree;
    }

    private BSTree.BSTNode forkJoin(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }
        BSTree.BSTNode node = new BSTree.BSTNode(arr[start]);
        int index = start + 1;
        while (index <= end) {
            if (arr[index] > arr[start]) {
                break;
            }
            index++;
        }
        node.left = forkJoin(arr, start + 1, index - 1);
        node.right = forkJoin(arr, index, end);
        return node;
    }
}
